cannibal = 'X'
missionary = 'O'

theNumberOfPeople = [0,1,2,3]
banks = [0,1]

initial_state = (3,3,0)
goal_state = (3,3,1)

subset_pairs = [(theNumberOfCannibal, theNumberOfMissionary, bank) for theNumberOfCannibal in theNumberOfPeople for theNumberOfMissionary in theNumberOfPeople for bank in banks]

def is_valid_state(state):
    theNumberOfCannibal, theNumberOfMissionary, bank = state

    if theNumberOfCannibal > theNumberOfMissionary and theNumberOfMissionary != 0:
    	return False
            
    if theNumberOfCannibal < theNumberOfMissionary and theNumberOfMissionary != 3:
        return False;
        
    return True

operators = {(1,0),(1,1),(2,0),(0,1),(0,2)}


def make_move(state, operator):
    theNumberOfCannibal, theNumberOfMissionary, bank = state
    theNumberOfCannibalOnBoat, theNumberOfMissionaryOnBoat = operator
    
    return (3 - theNumberOfCannibal + theNumberOfCannibalOnBoat, 3 - theNumberOfMissionary + theNumberOfMissionaryOnBoat, 1 - bank)

def is_valid_move(state, operator):
    
    theNumberOfCannibal, theNumberOfMissionary, bank = state
    theNumberOfCannibalOnBoat, theNumberOfMissionaryOnBoat = operator

    if theNumberOfCannibal < theNumberOfCannibalOnBoat or theNumberOfMissionary < theNumberOfMissionaryOnBoat:
    	return False
    
    return True

def valid_successors(state):
    succ = []
    for op in operators:
        next_state = make_move(state, op)
        if is_valid_move(state, op) and is_valid_state(next_state):
            succ.append((next_state, op))
    return succ

queue = [([initial_state], [])]
solutions = []


while len(queue) > 0:
	visited, oplist = queue.pop(0)
    
	current_state = visited[-1]
	for new_state, op in valid_successors(current_state):
	    new_visited = visited + [new_state]
	    new_oplist = oplist + [op]
	    if new_state == goal_state:
	        solutions.append((new_visited, new_oplist))
	    elif new_state not in visited:
	        queue.append((new_visited, new_oplist))

def print_solution_table(solution):
    
    def print_row(state, operator):
        theNumberOfCannibal, theNumberOfMissionary, bank = state
        theNumberOfCannibalOnTheLeft = theNumberOfCannibal
        theNumberOfMissionaryOnTheLeft = theNumberOfMissionary
        theNumberOfCannibalOnTheRight = 3 - theNumberOfCannibal
        theNumberOfMissionaryOnTheRight = 3 - theNumberOfMissionary
        if bank == 1:
            theNumberOfCannibalOnTheLeft = 3 - theNumberOfCannibalOnTheLeft
            theNumberOfMissionaryOnTheLeft = 3 - theNumberOfMissionaryOnTheLeft
            theNumberOfCannibalOnTheRight = 3 - theNumberOfCannibalOnTheRight
            theNumberOfMissionaryOnTheRight = 3 - theNumberOfMissionaryOnTheRight
        
        left = ""
        move = ""
        right = ""
        
        for i in range(0, theNumberOfCannibalOnTheLeft):
            left = left + cannibal + ", "
        for i in range(0, theNumberOfMissionaryOnTheLeft):
            left = left + missionary + ", "
        
        for i in range(0, theNumberOfCannibalOnTheRight):
            right = right + cannibal + ", "
        for i in range(0, theNumberOfMissionaryOnTheRight):
            right = right + missionary + ", "

        if bank == 0:
            left = left + "boat"
        else:
            right = right + "boat"
        
        if operator:
            theNumberOfCannibalOnBoat, theNumberOfMissionaryOnBoat = operator
            for i in range(0, theNumberOfCannibalOnBoat):
                move = move + cannibal + ", "
            for i in range(0, theNumberOfMissionaryOnBoat):
                move = move + missionary + ", "
            print '{0:30} {1:30} {2:30}'.format(left, right, move)
        else:
            print '{0:30} {1:30} {2:30}'.format(left, right, move)


    states, operators = solution
    print '{0:30} {1:30} {2:30}'.format("Left", "Right", "Move")
    for state, operator in zip(states, operators):
        print_row(state, operator)
    last_state = states[-1]
    print_row(last_state, None)
    return 0

print len(solutions), "possible solutions, one example:"
print_solution_table(solutions[2])












